package com.zwj.interview.动态规划;

import java.util.List;

/**
 * 题目：在一个由数字组成的三角形中，第1行有1个数字，第2行有2个数字，以此类推，第n行有n个数字
 *
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和
 *
 *    2
 *   3 4
 *  6 5 7
 * 4 1 8 3
 */
public class 三角形中最小路径之和 {

    /**
     * 分析：
     * 可以用f（i，j）表示从三角形的顶部出发到达行号和列号分别为i和j（i≥j）的位置时路径数字之和的最小值，
     * 同时用T[i][j]表示三角形行号和列号分别为i和j的数字。如果三角形中包含n行数字，
     * 那么f（n-1，j）的最小值就是整个问题的最优解
     * <p>
     * 如果j等于0，也就是当前到达某行的第1个数字。由于路径的每步都是前往正下方或右下方的数字，
     * 而此时当前位置的左上方没有数字，那么前一步是一定来自它的正上方的数字，
     * 因此f（i，0）等于f（i-1，0）与T[i][0]之和
     * <p>
     * 如果i等于j，也就是当前到达某行的最后一个数字，此时它的正上方没有数字，前一步只能是来自它左上方的数字，
     * 因此f（i，i）等于f（i-1，i-1）与T[i][i]之和
     * <p>
     * 如果当前行号和列号分别为i和j的位置位于某行的中间，那么前一步既可能是来自它正上方的数字（行号和列号分别为i-1和j），
     * 也可能是来自它左上方的数字（行号和列号分别为i-1和j-1），
     * 所以f（i，j）等于f（i-1，j）与f（i-1，j-1）的最小值再加上T[i][j]
     */

    public int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();
        int[][] dp = new int[size][size];
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j <= i; ++j) {
                //拿到某个位置的数字
                dp[i][j] = triangle.get(i).get(j);
                //走到某一行第一列数字，那么上一个数字只能是正上方的
                if (i > 0 && j == 0) {
                    dp[i][j] += dp[i - 1][j];
                    //走到某一行的最后一个数字，那么上一个数字只能是左上方的
                } else if (i > 0 && i == j) {
                    dp[i][j] += dp[i - 1][j - 1];
                } else if (i > 0) {
                    //来到某行的中间，就要取正上方和左上方的较小者
                    dp[i][j] += Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int num : dp[size - 1]) {
            min = Math.min(min, num);
        }
        return min;
    }




}